{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #String Transformation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #dynamic-programming #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #动态规划 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串转换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个长度都为 <code>n</code>&nbsp;的字符串&nbsp;<code>s</code> 和&nbsp;<code>t</code>&nbsp;。你可以对字符串 <code>s</code>&nbsp;执行以下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>将 <code>s</code>&nbsp;长度为 <code>l</code>&nbsp;（<code>0 &lt; l &lt; n</code>）的 <strong>后缀字符串</strong>&nbsp;删除，并将它添加在 <code>s</code>&nbsp;的开头。<br />\n",
    "\t比方说，<code>s = 'abcd'</code>&nbsp;，那么一次操作中，你可以删除后缀&nbsp;<code>'cd'</code>&nbsp;，并将它添加到&nbsp;<code>s</code>&nbsp;的开头，得到&nbsp;<code>s = 'cdab'</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>k</code>&nbsp;，请你返回&nbsp;<strong>恰好</strong> <code>k</code>&nbsp;次操作将<em>&nbsp;</em><code>s</code> 变为<em>&nbsp;</em><code>t</code>&nbsp;的方案数。</p>\n",
    "\n",
    "<p>由于答案可能很大，返回答案对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abcd\", t = \"cdab\", k = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "第一种方案：\n",
    "第一次操作，选择 index = 3 开始的后缀，得到 s = \"dabc\" 。\n",
    "第二次操作，选择 index = 3 开始的后缀，得到 s = \"cdab\" 。\n",
    "\n",
    "第二种方案：\n",
    "第一次操作，选择 index = 1 开始的后缀，得到 s = \"bcda\" 。\n",
    "第二次操作，选择 index = 1 开始的后缀，得到 s = \"cdab\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"ababab\", t = \"ababab\", k = 1\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "第一种方案：\n",
    "选择 index = 2 开始的后缀，得到 s = \"ababab\" 。\n",
    "\n",
    "第二种方案：\n",
    "选择 index = 4 开始的后缀，得到 s = \"ababab\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>15</sup></code></li>\n",
    "\t<li><code>s.length == t.length</code></li>\n",
    "\t<li><code>s</code> 和&nbsp;<code>t</code>&nbsp;都只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [string-transformation](https://leetcode.cn/problems/string-transformation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [string-transformation](https://leetcode.cn/problems/string-transformation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcd\"\\n\"cdab\"\\n2', '\"ababab\"\\n\"ababab\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        def minRep(s):\n",
    "            i = 0\n",
    "            N = len(s)\n",
    "            j = 1\n",
    "            while j < N:\n",
    "                for k in range(N):\n",
    "                    a = s[(i + k) % N]\n",
    "                    b = s[(j + k) % N]\n",
    "                    if a == b:\n",
    "                        continue\n",
    "                    elif a > b:\n",
    "                        i, j = j, max(i + k + 1, j + 1)\n",
    "                        break\n",
    "                    else:\n",
    "                        j = j + k + 1\n",
    "                        break\n",
    "                else:\n",
    "                    return i, j - i\n",
    "            return i, N\n",
    "        si, sm = minRep(s)\n",
    "        ti, tm = minRep(t)\n",
    "        if s[si:] + s[:si] != t[ti:] + t[:ti]:\n",
    "            return 0\n",
    "        N = len(s)\n",
    "        # si + \\Sum X_k \\equiv ti (mod sm)\n",
    "        MOD = 1000000007\n",
    "        # F0 = (si == ti)\n",
    "        # Fk = N^k / sm\n",
    "        # Fk = N^k / sm - C(k, 1)N^(k-1) / sm + C(k, 2)N^(k-2)...\n",
    "        # ((N - 1)^k - (-1)^k F0) / sm\n",
    "        return ((pow(N - 1, k, MOD) + pow(-1, k % 2) * ((si == ti) * sm - 1)) * pow(sm, MOD - 2, MOD)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        z=10**9+7 \n",
    "        n=len(s)\n",
    "        \n",
    "        @cache    \n",
    "        def q(d,k):\n",
    "            if k==1:\n",
    "                return d!=0\n",
    "            else:\n",
    "                return ((n-2)*q(d,k//2)*q(d,k-k//2)+q(0,k//2)*q(d,k-k//2)+q(d,k//2)*q(0,k-k//2) if d!=0 else (n-1)*q(1,k//2)*q(1,k-k//2)+q(0,k//2)*q(0,k-k//2))%z\n",
    "\n",
    "        s2=s+s\n",
    "        x,y=0,1\n",
    "        while y<n and s2[y:y+n]!=s:\n",
    "            y+=1\n",
    "        while x<n and s2[x:x+n]!=t:\n",
    "            x+=1\n",
    "        if x<n:\n",
    "            return (q(1,k)*(n//y-(x==0))+(x==0)*q(0,k))%z\n",
    "        else:\n",
    "            return 0       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class RabinKarp:\n",
    "    DEBUG = False\n",
    "    mod = 67280421310721  # int(1e9)+7\n",
    "    if DEBUG:\n",
    "        big_primes = [10]\n",
    "        to_int = int\n",
    "    else:\n",
    "        big_primes = [16777619]\n",
    "        to_int = ord\n",
    "\n",
    "    ex_gcd = []\n",
    "    for i in big_primes:\n",
    "        ex_gcd.append(pow(i, mod - 2, mod))\n",
    "\n",
    "    def __init__(self, ss=None):\n",
    "        from collections import deque\n",
    "        self.hash = [0 for _ in RabinKarp.big_primes]\n",
    "        self.string = deque()\n",
    "        if ss is not None:\n",
    "            for i in ss:\n",
    "                self.append(i)\n",
    "\n",
    "    def append(self, char):\n",
    "        for i in range(len(RabinKarp.big_primes)):\n",
    "            self.hash[i] = ((self.hash[i] * RabinKarp.big_primes[i]) + RabinKarp.to_int(char)) % RabinKarp.mod\n",
    "        self.string.append(char)\n",
    "        return self\n",
    "\n",
    "    def appendleft(self, char):\n",
    "        for i in range(len(RabinKarp.big_primes)):\n",
    "            self.hash[i] += pow(RabinKarp.big_primes[i], len(self.string), RabinKarp.mod) * RabinKarp.to_int(char)\n",
    "            self.hash[i] %= RabinKarp.mod\n",
    "        self.string.appendleft(char)\n",
    "        return self\n",
    "\n",
    "    def pop(self):\n",
    "        char = self.string.pop()\n",
    "        for i in range(len(RabinKarp.big_primes)):\n",
    "            self.hash[i] = ((self.hash[i] - RabinKarp.to_int(char)) * RabinKarp.ex_gcd[i]) % RabinKarp.mod\n",
    "        return self\n",
    "\n",
    "    def popleft(self):\n",
    "        char = self.string.popleft()\n",
    "        for i in range(len(RabinKarp.big_primes)):\n",
    "            self.hash[i] -= pow(RabinKarp.big_primes[i], len(self.string), RabinKarp.mod) * RabinKarp.to_int(char)\n",
    "            self.hash[i] %= RabinKarp.mod\n",
    "        return self\n",
    "\n",
    "    def hash_value(self):\n",
    "        return tuple(self.hash)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str({\"string\": ''.join(self.string), \"hash\": self.hash_value()})\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        t_hash = RabinKarp(t).hash_value()\n",
    "        s_hash = RabinKarp(s)\n",
    "        good = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if t_hash == s_hash.hash_value():\n",
    "                good += 1\n",
    "            chr = s_hash.string[-1]\n",
    "            s_hash.pop()\n",
    "            s_hash.appendleft(chr)\n",
    "        grid = [[good - 1, good], [len(s) - good, len(s) - good - 1]]\n",
    "        mod = int(1e9)+7\n",
    "        def dot(matrix1, matrix2):\n",
    "            if len(matrix1[0]) != len(matrix2):\n",
    "                raise ValueError\n",
    "            ans = [[0 for _ in matrix2[0]] for _ in matrix1]\n",
    "            for x in range(len(ans)):\n",
    "                for y in range(len(ans[0])):\n",
    "                    for i in range(len(matrix1[0])):\n",
    "                        ans[x][y] += matrix1[x][i] * matrix2[i][y]\n",
    "                        ans[x][y] %= mod\n",
    "            return ans\n",
    "\n",
    "        def q_pow(matrix, b):\n",
    "            ans = matrix\n",
    "            b -= 1\n",
    "            while b > 0:\n",
    "                if b & 1:\n",
    "                    ans = dot(ans, matrix)\n",
    "                matrix = dot(matrix, matrix)\n",
    "                b >>= 1\n",
    "            return ans\n",
    "\n",
    "        grid = q_pow(grid, k)\n",
    "        return grid[0][0] if s == t else grid[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_000 + 7\n",
    "MOD2 = 998244353\n",
    "\n",
    "\n",
    "def matmul(a1, a2):\n",
    "    n = len(a1)\n",
    "    res = [[0]*n for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            for k in range(n):\n",
    "                res[i][j] = (res[i][j] + a1[i][k] * a2[k][j]) % MOD\n",
    "    return res\n",
    "\n",
    "def quickmatmul(a, n):\n",
    "    res = [[0]*len(a) for _ in range(len(a))]\n",
    "    for i in range(len(a)):\n",
    "        res[i][i] = 1\n",
    "    base = a\n",
    "    while n:\n",
    "        if (n & 1):\n",
    "            res = matmul(res, base)\n",
    "        base = matmul(base, base)\n",
    "        n >>= 1\n",
    "    return res\n",
    "    \n",
    "        \n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        P1, P2 = 131, 137\n",
    "\n",
    "        n = len(s)\n",
    "        F1 = F2 = 1\n",
    "        for i in range(n):\n",
    "            F1 = F1 * P1 % MOD\n",
    "            F2 = F2 * P2 % MOD2\n",
    "        goal1 = goal2 = 0;\n",
    "        for c in t:\n",
    "            goal1 = (goal1 * P1 + ord(c)-ord('a')) % MOD\n",
    "            goal2 = (goal2 * P2 + ord(c)-ord('a')) % MOD2\n",
    "\n",
    "        # 通过字符串哈希求出哪些下标是好的，good[i] 表示下标 i 是好的\n",
    "        good = [0]*n\n",
    "        now1 = now2 = 0\n",
    "        for c in s:\n",
    "            now1 = (now1 * P1 + ord(c)-ord('a')) % MOD\n",
    "            now2 = (now2 * P2 + ord(c)-ord('a')) % MOD2\n",
    "        for i in range(n):\n",
    "            if (now1 == goal1 and now2 == goal2):\n",
    "                good[i] = True\n",
    "            if i == n - 1:\n",
    "                break\n",
    "            now1 = (now1 * P1 + ord(s[i])-ord('a')) % MOD;\n",
    "            now2 = (now2 * P2 + ord(s[i])-ord('a')) % MOD2;\n",
    "            now1 = (now1 - F1 * (ord(s[i])-ord('a')) % MOD + MOD) % MOD\n",
    "            now2 = (now2 - F2 * (ord(s[i])-ord('a')) % MOD2 + MOD2) % MOD2\n",
    "\n",
    "        goodCnt = 0\n",
    "        for i in range(n):\n",
    "            if good[i]:\n",
    "                goodCnt += 1\n",
    "\n",
    "        K = [[0]*2 for  _ in range(2)]\n",
    "        K[0][0] = n - goodCnt - 1\n",
    "        K[0][1] = goodCnt;\n",
    "        K[1][0] = n - goodCnt\n",
    "        K[1][1] = goodCnt - 1\n",
    "        \n",
    "        K = quickmatmul(K, k)\n",
    "\n",
    "        A = [[0]*2 for  _ in range(2)]\n",
    "        A[0][0] = 0 if good[0] else 1\n",
    "        A[0][1] = 1 if good[0] else 0\n",
    "        A = matmul(A, K) \n",
    "        return A[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, K: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        def kmp_init(t):\n",
    "            n = len(t)\n",
    "            nxt = [-1] * n\n",
    "            j, k = 0, -1\n",
    "            while j < n - 1:\n",
    "                if k == -1 or t[j] == t[k]:\n",
    "                    k += 1\n",
    "                    j += 1\n",
    "                    nxt[j] = k if t[j] != t[k] else nxt[k]\n",
    "                else:\n",
    "                    k = nxt[k]\n",
    "            return nxt\n",
    "\n",
    "        def mul(a, b):\n",
    "            res = [[0, 0], [0, 0]]\n",
    "            for i in range(2):\n",
    "                for j in range(2):\n",
    "                    tot = 0\n",
    "                    for k in range(2):\n",
    "                        tot += a[i][k] * b[k][j]\n",
    "                    res[i][j] = tot % MOD\n",
    "            return res\n",
    "                    \n",
    "        def matrix_pow(d, K):\n",
    "            if not K:\n",
    "                return [[1, 0], [0, 1]]\n",
    "            if K == 1:\n",
    "                return d\n",
    "            mat = matrix_pow(d, K >> 1)\n",
    "            res = mul(mat, mat)\n",
    "            if K & 1:\n",
    "                res = mul(res, d)\n",
    "            return res\n",
    "        \n",
    "        def calc(L):\n",
    "            d = [[0, L-1], [1, L-2]]\n",
    "            return matrix_pow(d, K)\n",
    "        \n",
    "        t += '$'\n",
    "        n = len(t)\n",
    "        nxt = kmp_init(t)\n",
    "        L = len(s)\n",
    "        mat = calc(L)\n",
    "        ss = s + s[:L-1]\n",
    "        m = len(ss)\n",
    "        res = 0\n",
    "        i, j = 0, 0\n",
    "        while i < m and j < n:\n",
    "            if j == -1 or ss[i] == t[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                if j == n - 1:\n",
    "                    start = i - n + 1\n",
    "                    if not start:\n",
    "                        res = (res + mat[0][0]) % MOD\n",
    "                    else:\n",
    "                        res = (res + mat[1][0]) % MOD\n",
    "            else:\n",
    "                j = nxt[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        m1 = 100007\n",
    "        m2 = 10000007\n",
    "        a1 = 26\n",
    "        a2 = 37\n",
    "        def gv(c):\n",
    "            return ord(c) - ord('a')\n",
    "        def hs(a, a1, m1):\n",
    "            r = 0\n",
    "            for c in a:\n",
    "                r = r * a1 + gv(c)\n",
    "                r %= m1\n",
    "            return r\n",
    "        hs1 = hs(s, a1, m1)\n",
    "        hs2 = hs(s, a2, m2)\n",
    "        ht1 = hs(t, a1, m1)\n",
    "        ht2 = hs(t, a2, m2)\n",
    "        ma = [0] * len(s)\n",
    "        a1e = pow(a1, len(s), m1)\n",
    "        a2e = pow(a2, len(s), m2)\n",
    "\n",
    "        for i, c in enumerate(t):\n",
    "            if ht1 == hs1 and ht2 == hs2:\n",
    "                ma[i] = 1\n",
    "            ht1 = (ht1 * a1 - gv(c) * a1e + gv(c)) % m1\n",
    "            ht2 = (ht2 * a2 - gv(c) * a2e + gv(c)) % m2\n",
    "        temp = [[0, 0], [0, 0]]\n",
    "        p = int(1e9 + 7)\n",
    "        l = len(s)\n",
    "        def mm(a, b):\n",
    "            for i in range(2):\n",
    "                for j in range(2):\n",
    "                    temp[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]\n",
    "                    temp[i][j] %= p\n",
    "            return (tuple(temp[0]), tuple(temp[1]))\n",
    "        def mpow(a, n):\n",
    "            r = ((1, 0), (0, 1))\n",
    "            while n:\n",
    "                if n & 1:\n",
    "                    r = mm(r, a)\n",
    "                a = mm(a, a)\n",
    "                n >>= 1\n",
    "            return r\n",
    "        r = mpow(((0, 1), (l - 1, l - 2)), k - 1)\n",
    "        ans = r[1][0] if ma[0] == 1 else 0\n",
    "        ans += sum(ma[1:]) * r[1][1]\n",
    "        return ans % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    \n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        '''\n",
    "        n = 4\n",
    "        d = 2\n",
    "        \n",
    "        k = 4 总共移动2, 6, 10\n",
    "        实际上只需要1次就可以让s和t相等\n",
    "        所以前k-1次落在哪儿都无所谓, 只要不和t相等就可以了\n",
    "        \n",
    "        以第一个字母为例, 移动的次数为0<l<n, 这时候需要统计有多少个位置可以不相等\n",
    "        假设有m个位置\n",
    "        那么每次移动可以选择 m-1个方案(不能不动)\n",
    "        由于一开始有可能s==t, 那么可以选择的方案就是m个\n",
    "        \n",
    "        总共就是(m-1) ^ (k-1) * (n-m)个方案\n",
    "        '''\n",
    "        \n",
    "        '''\n",
    "        如果t最小旋转a次就可以变成t\n",
    "        那么t中有长度为a重复子数组 \n",
    "        '''\n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(t)\n",
    "        \n",
    "        \n",
    "        def isSame(a, b):\n",
    "            if len(a) != len(b):\n",
    "                return False\n",
    "            \n",
    "            i = 0\n",
    "            while i < n:\n",
    "                same = True\n",
    "                for j in range(n):\n",
    "                    if s[(i+j)%n] != t[j]:\n",
    "                        same = False\n",
    "                        break\n",
    "                if same:\n",
    "                    return True\n",
    "                i += 1\n",
    "            return False\n",
    "        \n",
    "        if not isSame(s,t):\n",
    "            return 0\n",
    "        # 计算一个节的长度\n",
    "        m = inf\n",
    "        for l in range(1, n+1):\n",
    "            if n % l != 0:\n",
    "                continue\n",
    "            start = l\n",
    "            end=l+l\n",
    "            yes = True\n",
    "            while start < n:\n",
    "                if t[0:l] != t[start:end]:\n",
    "                    yes = False\n",
    "                    break\n",
    "                start += l\n",
    "                end += l\n",
    "            if yes:\n",
    "                m = l\n",
    "                break\n",
    "\n",
    "        \n",
    "        '''\n",
    "        x 是 节数\n",
    "        相同 -> 相同: x-1\n",
    "        不同 -> 相同: x\n",
    "        相同 -> 不同: n-x\n",
    "        不同 -> 不同: n-x-1\n",
    "        '''\n",
    "        def getpow(a, b, base, num):\n",
    "            ans = base\n",
    "            mat = np.array([[a-1, a],[b, b-1]])\n",
    "            for i in range(64):\n",
    "                if (1 << i) & num:\n",
    "                    ans = mat @ ans\n",
    "                    ans %= MOD\n",
    "                mat = mat @ mat\n",
    "                mat %= MOD\n",
    "            return ans\n",
    "\n",
    "        x = n // m\n",
    "        if s == t:\n",
    "            return getpow(x, n-x, np.array([[1],[0]]), k)[0].item()\n",
    "        return getpow(x, n-x, np.array([[0],[1]]), k)[0].item()\n",
    "        \n",
    "        \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        def power(p, x, e):\n",
    "            base = x\n",
    "            answer = 1\n",
    "            while e:\n",
    "                if e & 1:\n",
    "                    answer = (answer * base) % p\n",
    "\n",
    "                base = (base * base) % p\n",
    "                e >>= 1\n",
    "\n",
    "            return answer\n",
    "        \n",
    "        def inv(p, x):\n",
    "            return power(p, x, p - 2)\n",
    "\n",
    "        \n",
    "        P = 10**9 + 7\n",
    "        MOD = 2**63 - 25\n",
    "        INV = inv(MOD, 26)\n",
    "        \n",
    "        char_dict = {chr(ord('a') + i): i for i in range(26)}\n",
    "        \n",
    "        def new_hash(s):\n",
    "            answer = 0\n",
    "            p = 1\n",
    "            \n",
    "            for c in s:\n",
    "                answer = (answer + char_dict[c] * p) % MOD\n",
    "                p = (p * 26) % MOD\n",
    "                \n",
    "            return answer\n",
    "        \n",
    "        ht = new_hash(t)\n",
    "        good = []\n",
    "        \n",
    "        n = len(s)\n",
    "        SH = (1 - power(MOD, 26, n)) % MOD\n",
    "        \n",
    "        hs = new_hash(s)\n",
    "        for i in range(n):\n",
    "            if hs == ht:\n",
    "                good.append(i)\n",
    "                \n",
    "            c = char_dict[s[n - 1 - i]]\n",
    "            hs = (26 * hs + c * SH) % MOD\n",
    "            \n",
    "        if not good:\n",
    "            return 0\n",
    "        \n",
    "        zero = 1 if good[0] == 0 else 0\n",
    "        nz = len(good) - zero\n",
    "        \n",
    "        v1 = (power(P, n - 1, k) - (-1)**k) * inv(P, n)\n",
    "        v0 = v1 + (-1)**k\n",
    "        \n",
    "        return (zero * v0 + nz * v1) % P\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        c = self.kmp_search(s + s[:-1], t)\n",
    "        m = [\n",
    "            [c - 1, c],\n",
    "            [n - c, n - 1 - c]\n",
    "        ]\n",
    "        m = self.pow(m, k)\n",
    "        return m[0][s != t]\n",
    "\n",
    "\n",
    "    # KMP 模板\n",
    "    def calc_max_match(self, s: str) -> List[int]:\n",
    "        match = [0] * len(s)\n",
    "        c = 0\n",
    "        for i in range(1, len(s)):\n",
    "            v = s[i]\n",
    "            while c and s[c] != v:\n",
    "                c = match[c - 1]\n",
    "            if s[c] == v:\n",
    "                c += 1\n",
    "            match[i] = c\n",
    "        return match\n",
    "    \n",
    "    # KMP 模板\n",
    "    # 返回 text 中出现了多少次 pattern（允许 pattern 重叠）\n",
    "    def kmp_search(self, text: str, pattern: str) -> int:\n",
    "        match = self.calc_max_match(pattern)\n",
    "        match_cnt = c = 0\n",
    "        for i, v in enumerate(text):\n",
    "            while c and pattern[c] != v:\n",
    "                c = match[c - 1]\n",
    "            if pattern[c] == v:\n",
    "                c += 1\n",
    "            if c == len(pattern):\n",
    "                match_cnt += 1\n",
    "                c = match[c - 1]\n",
    "        return match_cnt\n",
    "    \n",
    "    # 矩阵乘法\n",
    "    def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:\n",
    "        c = [[0, 0], [0, 0]]\n",
    "        for i in range(2):\n",
    "            for j in range(2):\n",
    "                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (10 ** 9 + 7)\n",
    "        return c\n",
    "\n",
    "    # 矩阵快速幂\n",
    "    def pow(self, a: List[List[int]], n: int) -> List[List[int]]:\n",
    "        res = [[1, 0], [0, 1]]\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                res = self.multiply(res, a)\n",
    "            a = self.multiply(a, a)\n",
    "            n //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s, t, k):\n",
    "        n = len(s)\n",
    "        c = self.kmp_search(s + s[:-1], t)\n",
    "        m = [\n",
    "            [c - 1, c],\n",
    "            [n - c, n - 1 - c]\n",
    "        ]\n",
    "        m = self.pow(m, k)\n",
    "        return m[0][s != t]\n",
    "\n",
    "    # KMP 模板\n",
    "    def calc_max_match(self, s: str) -> List[int]:\n",
    "        match = [0] * len(s)\n",
    "        c = 0\n",
    "        for i in range(1, len(s)):\n",
    "            v = s[i]\n",
    "            while c and s[c] != v:\n",
    "                c = match[c - 1]\n",
    "            if s[c] == v:\n",
    "                c += 1\n",
    "            match[i] = c\n",
    "        return match\n",
    "\n",
    "    # KMP 模板\n",
    "    # 返回 text 中出现了多少次 pattern（允许 pattern 重叠）\n",
    "    def kmp_search(self, text: str, pattern: str) -> int:\n",
    "        match = self.calc_max_match(pattern)\n",
    "        match_cnt = c = 0\n",
    "        for i, v in enumerate(text):\n",
    "            v = text[i]\n",
    "            while c and pattern[c] != v:\n",
    "                c = match[c - 1]\n",
    "            if pattern[c] == v:\n",
    "                c += 1\n",
    "            if c == len(pattern):\n",
    "                match_cnt += 1\n",
    "                c = match[c - 1]\n",
    "        return match_cnt\n",
    "\n",
    "    # 矩阵乘法\n",
    "    def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:\n",
    "        c = [[0, 0], [0, 0]]\n",
    "        for i in range(2):\n",
    "            for j in range(2):\n",
    "                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (10 ** 9 + 7)\n",
    "        return c\n",
    "\n",
    "    # 矩阵快速幂\n",
    "    def pow(self, a: List[List[int]], n: int) -> List[List[int]]:\n",
    "        res = [[1, 0], [0, 1]]\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                res = self.multiply(res, a)\n",
    "            a = self.multiply(a, a)\n",
    "            n //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        mod = 10 ** 9 + 7 \n",
    "        \n",
    "        def build(p):\n",
    "            j = 0\n",
    "            nxt = [0, 0]\n",
    "            for i in range(1, len(p)):\n",
    "                while j > 0 and p[i] != p[j]:\n",
    "                    j = nxt[j]\n",
    "                if p[i] == p[j]:\n",
    "                    j += 1 \n",
    "                nxt.append(j)\n",
    "            return nxt \n",
    "        def match(s, p):\n",
    "            nxt = build(p)\n",
    "            j = 0\n",
    "            c = 0\n",
    "            for i in range(len(s)):\n",
    "                while j > 0 and p[j] != s[i]:\n",
    "                    j = nxt[j]\n",
    "                if s[i] == p[j]:\n",
    "                    j += 1 \n",
    "                    if j == len(p):\n",
    "                        c += 1 \n",
    "                        j = nxt[j]\n",
    "            return c \n",
    "        c = match((s + s)[:-1], t)\n",
    "        M = [[c - 1, c], [n - 1 - c + 1, n - 1 - c]]\n",
    "        def matrix_multiple(A, B):\n",
    "            C = [[0, 0], [0, 0]]\n",
    "            for i in range(2):\n",
    "                for j in range(2):\n",
    "                    C[i][j] = (A[i][0] * B[0][j] + A[i][1] * B[1][j]) % mod\n",
    "            return C \n",
    "        def quick_pow(M, n):\n",
    "            res = [[1, 0], [0, 1]]\n",
    "            while n:\n",
    "                if n % 2:\n",
    "                    res = matrix_multiple(res, M)\n",
    "                M = matrix_multiple(M, M)\n",
    "                n //= 2 \n",
    "            return res \n",
    "        res = quick_pow(M, k)\n",
    "        return res[0][0] if s == t else res[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def matrix_pow(a: List[List[int]], k: int) -> List[List[int]]:\n",
    "    m = len(a)\n",
    "    n = len(a[0])\n",
    "    res = [[0] * m for _ in range(m)]\n",
    "    for i in range(m):\n",
    "        res[i][i] = 1\n",
    "    while k > 0:\n",
    "        if k & 1:\n",
    "            res = matrix_mul(res, a)\n",
    "        a = matrix_mul(a, a)\n",
    "        k >>= 1\n",
    "    return res\n",
    "\n",
    "\n",
    "def matrix_mul(a: List[List[int]], b: List[List[int]], mod: int = 10**9 + 7):\n",
    "    m = len(a)\n",
    "    n = len(a[0])\n",
    "    p = len(b[0])\n",
    "    c = [[0] * p for _ in range(n)]\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            for k in range(p):\n",
    "                c[i][k] = (c[i][k] + a[i][j] * b[j][k]) % mod\n",
    "\n",
    "    return c\n",
    "\n",
    "\n",
    "# KMP 模板\n",
    "def calc_max_match(s: str) -> List[int]:\n",
    "    match = [0] * len(s)\n",
    "    c = 0\n",
    "    for i in range(1, len(s)):\n",
    "        v = s[i]\n",
    "        while c and s[c] != v:\n",
    "            c = match[c - 1]\n",
    "        if s[c] == v:\n",
    "            c += 1\n",
    "        match[i] = c\n",
    "    return match\n",
    "\n",
    "\n",
    "# KMP 模板\n",
    "# 返回 text 中出现了多少次 pattern（允许 pattern 重叠）\n",
    "def kmp_search(text: str, pattern: str) -> int:\n",
    "    match = calc_max_match(pattern)\n",
    "    match_cnt = c = 0\n",
    "    for i, v in enumerate(text):\n",
    "        v = text[i]\n",
    "        while c and pattern[c] != v:\n",
    "            c = match[c - 1]\n",
    "        if pattern[c] == v:\n",
    "            c += 1\n",
    "        if c == len(pattern):\n",
    "            match_cnt += 1\n",
    "            c = match[c - 1]\n",
    "    return match_cnt\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        ss = s + s\n",
    "        if t not in ss:\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        q = kmp_search((s + s)[:-1], t)\n",
    "        res = matrix_pow([[q - 1, q], [n - q, n - q - 1]], k)\n",
    "\n",
    "        return res[0][0] if s == t else res[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        # text 中，有多少 pattern 个\n",
    "        def kmp2(text: str, pattern: str) -> int:\n",
    "            next = [0] * len(text)\n",
    "            j = 0\n",
    "            for i in range(1, len(pattern)):\n",
    "                while j > 0 and pattern[j] != pattern[i]:\n",
    "                    j = next[j - 1]\n",
    "                if pattern[j] == pattern[i]:\n",
    "                    j += 1\n",
    "                next[i] = j\n",
    "            cnt = j = 0\n",
    "            print(len(text))\n",
    "            for i, v in enumerate(text):\n",
    "                while j > 0 and pattern[j] != v:\n",
    "                    j = next[j - 1]\n",
    "                if pattern[j] == v:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    cnt += 1\n",
    "                    j = next[j - 1]\n",
    "                    # print(i, j, cnt)\n",
    "            return cnt\n",
    "        def kmp(text: str, pattern: str) -> int:\n",
    "            pmt = [0] * n\n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and t[i] != t[j]:\n",
    "                    j = pmt[j - 1]\n",
    "                if t[i] == t[j]:\n",
    "                    j += 1\n",
    "                pmt[i] = j\n",
    "            print(pmt)\n",
    "            j = 0\n",
    "            cnt = 0\n",
    "            for i in range(n*2-1):\n",
    "                while j > 0 and s[i%n] != t[j]:\n",
    "                    j = pmt[j - 1]\n",
    "                if s[i%n] == t[j]:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    cnt += 1\n",
    "                    j = pmt[j - 1]\n",
    "                    print(i, j, cnt)\n",
    "\n",
    "            return cnt\n",
    "        n = len(s)\n",
    "        c = kmp2(s + s[:-1], t)\n",
    "        \n",
    "        m = [\n",
    "            [c - 1, c],\n",
    "            [n - c, n - 1 - c]\n",
    "        ]\n",
    "        m = self.pow(m, k)\n",
    "        return m[0][s != t]\n",
    "    # 矩阵乘法\n",
    "    def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:\n",
    "        c = [[0, 0], [0, 0]]\n",
    "        for i in range(2):\n",
    "            for j in range(2):\n",
    "                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (10 ** 9 + 7)\n",
    "        return c\n",
    "\n",
    "    # 矩阵快速幂\n",
    "    def pow(self, a: List[List[int]], n: int) -> List[List[int]]:\n",
    "        res = [[1, 0], [0, 1]]\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                res = self.multiply(res, a)\n",
    "            a = self.multiply(a, a)\n",
    "            n //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        # text 中，有多少 pattern 个\n",
    "        def kmp2(text: str, pattern: str) -> int:\n",
    "            next = [0] * len(text)\n",
    "            j = 0\n",
    "            for i in range(1, len(pattern)):\n",
    "                while j > 0 and pattern[j] != pattern[i]:\n",
    "                    j = next[j - 1]\n",
    "                if pattern[j] == pattern[i]:\n",
    "                    j += 1\n",
    "                next[i] = j\n",
    "            cnt = j = 0\n",
    "            #print(len(text))\n",
    "            for i, v in enumerate(text):\n",
    "                while j > 0 and pattern[j] != v:\n",
    "                    j = next[j - 1]\n",
    "                if pattern[j] == v:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    cnt += 1\n",
    "                    j = next[j - 1]\n",
    "                    # print(i, j, cnt)\n",
    "            return cnt\n",
    "        def kmp(text: str, pattern: str) -> int:\n",
    "            pmt = [0] * n\n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and t[i] != t[j]:\n",
    "                    j = pmt[j - 1]\n",
    "                if t[i] == t[j]:\n",
    "                    j += 1\n",
    "                pmt[i] = j\n",
    "            print(pmt)\n",
    "            j = 0\n",
    "            cnt = 0\n",
    "            for i in range(n*2-1):\n",
    "                while j > 0 and s[i%n] != t[j]:\n",
    "                    j = pmt[j - 1]\n",
    "                if s[i%n] == t[j]:\n",
    "                    j += 1\n",
    "                if j == n:\n",
    "                    cnt += 1\n",
    "                    j = pmt[j - 1]\n",
    "                    print(i, j, cnt)\n",
    "\n",
    "            return cnt\n",
    "        n = len(s)\n",
    "        c = kmp2(s + s[:-1], t)\n",
    "        \n",
    "        m = [\n",
    "            [c - 1, c],\n",
    "            [n - c, n - 1 - c]\n",
    "        ]\n",
    "        m = self.pow(m, k)\n",
    "        return m[0][s != t]\n",
    "    # 矩阵乘法\n",
    "    def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:\n",
    "        c = [[0, 0], [0, 0]]\n",
    "        for i in range(2):\n",
    "            for j in range(2):\n",
    "                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (10 ** 9 + 7)\n",
    "        return c\n",
    "\n",
    "    # 矩阵快速幂\n",
    "    def pow(self, a: List[List[int]], n: int) -> List[List[int]]:\n",
    "        res = [[1, 0], [0, 1]]\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                res = self.multiply(res, a)\n",
    "            a = self.multiply(a, a)\n",
    "            n //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        mod2=998244353\n",
    "        n=len(s)\n",
    "        ans=[]\n",
    "        res=0\n",
    "        a=0\n",
    "        b=0\n",
    "        for i in range(n):\n",
    "            a*=26\n",
    "            a+=ord(s[i])-ord('a')\n",
    "            a%=mod2\n",
    "            b*=26\n",
    "            b+=ord(t[i])-ord('a')\n",
    "            b%=mod2\n",
    "        kk=pow(26,n-1,mod2)\n",
    "            \n",
    "        for i in range(n):\n",
    "            if a==b:\n",
    "                ans.append(i)\n",
    "            a-=(ord(s[i])-ord('a'))*kk\n",
    "            a*=26\n",
    "            a+=ord(s[i])-ord(\"a\")\n",
    "            a%=mod2\n",
    "        cur=pow(n-1,k,n*mod)\n",
    "\n",
    "        print(ans)\n",
    "        if n==2:\n",
    "            res=0\n",
    "            for x in ans:\n",
    "                if x==0:\n",
    "                    res+=(k+1)&1\n",
    "                else:\n",
    "                    res+=k&1\n",
    "            return res%mod\n",
    "        print(cur)\n",
    "        if cur%n==1:\n",
    "            res+=(cur//n)*len(ans)\n",
    "            res%=mod\n",
    "            if 0 in ans:\n",
    "                res+=1\n",
    "                res%=mod\n",
    "        elif cur%n==n-1:\n",
    "            res+=((cur+1)//n)*len(ans)\n",
    "            res%=mod\n",
    "            if 0 in ans:\n",
    "                res-=1\n",
    "                res%=mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        def cal_max_match(pattern):\n",
    "            n = len(pattern)\n",
    "            pre = [0] * n \n",
    "            for i in range(1, n):\n",
    "                pre_i = pre[i-1]\n",
    "                while pre_i != 0 and pattern[pre_i] != pattern[i]:\n",
    "                    pre_i = pre[pre_i-1]\n",
    "                if pattern[pre_i] == pattern[i]:\n",
    "                    pre_i += 1\n",
    "                pre[i] = pre_i\n",
    "            return pre \n",
    "    \n",
    "        def kmp_search(target, pattern):\n",
    "            pre = cal_max_match(pattern)\n",
    "            print(pre)\n",
    "            match_cnt = 0\n",
    "            pos_p = 0\n",
    "            for char_t in target:\n",
    "                while pos_p and char_t != pattern[pos_p]:\n",
    "                    pos_p = pre[pos_p-1]\n",
    "                if pattern[pos_p] == char_t:\n",
    "                    pos_p += 1\n",
    "                if pos_p == n:\n",
    "                    match_cnt += 1\n",
    "                    pos_p = pre[pos_p-1]\n",
    "            return match_cnt \n",
    "        \n",
    "        def matrix_multiply(a:List[List[int]], b:List[List[int]]):\n",
    "            ans = [[0, 0], [0, 0]]\n",
    "            for i in range(2):\n",
    "                for j in range(2):\n",
    "                    ans[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (10**9+7)\n",
    "            return ans \n",
    "        \n",
    "        def matrix_pow(a : List[List[int]], n):\n",
    "            if n == 1:\n",
    "                return a\n",
    "            if n % 2== 0:\n",
    "                res = matrix_pow(a, n //2)\n",
    "                pow_part = matrix_multiply(res, res)\n",
    "                return pow_part\n",
    "            else:\n",
    "                return matrix_multiply(matrix_pow(a, n-1), a)\n",
    "         \n",
    "        c = kmp_search(s+s[:-1], t)\n",
    "        print(c)\n",
    "        boundary = [[1, 0], [0, 1]]\n",
    "        m = [[c-1, c],\n",
    "             [n-c, n-1-c]]\n",
    "        m = matrix_pow(m, k)\n",
    "        ans = matrix_multiply(m, boundary)\n",
    "        return ans[0][s!=t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "\n",
    "class KMP:\n",
    "    def __init__(self, pattern):\n",
    "        n = len(pattern)\n",
    "        self.nxt = [-1]*(n)\n",
    "        self.pattern = pattern\n",
    "        for i in range(n-1):\n",
    "            j = self.nxt[i]\n",
    "            while pattern[i+1] != pattern[j+1] and j != -1:\n",
    "                j = self.nxt[j]\n",
    "            if pattern[j+1] == pattern[i+1]:\n",
    "                j += 1\n",
    "            self.nxt[i+1] = j\n",
    "        # print(self.nxt)\n",
    "\n",
    "    def find(self, s):\n",
    "        n = len(s)\n",
    "        m = len(self.pattern)\n",
    "        ans = [0]*n \n",
    "        j = -1\n",
    "        for i, ch in enumerate(s):\n",
    "            while (j+1 == m or ch != self.pattern[j+1]) and j != -1:\n",
    "                j = self.nxt[j]\n",
    "            if ch == self.pattern[j+1]:\n",
    "                j += 1\n",
    "            if j+1 == m:\n",
    "                ans[i] = 1 \n",
    "        return ans \n",
    "\n",
    "def matmul(A,B):\n",
    "    n, k = len(A), len(A[0])\n",
    "    k, m = len(B), len(B[0])\n",
    "    C = [[0]*m for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            for p in range(k):\n",
    "                C[i][j] += A[i][p]*B[p][j]\n",
    "            C[i][j] %= MOD \n",
    "    return C \n",
    "\n",
    "def quickmul(A, q):\n",
    "    ans = [[1,0],[0,1]]\n",
    "    while q:\n",
    "        if q&1:\n",
    "            ans = matmul(ans,A)\n",
    "        q >>= 1\n",
    "        A = matmul(A,A)\n",
    "    return ans \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, pattern: str, t: str, k: int) -> int:\n",
    "        kmp = KMP(pattern)\n",
    "        n = len(t)\n",
    "        state = kmp.find(t+t)\n",
    "        # print(state)\n",
    "        cnt = sum(state[n:])\n",
    "        flag = state[n-1]\n",
    "        \n",
    "        A = [[n-cnt-1,n-cnt],[cnt,cnt-1]]\n",
    "        # print(A)\n",
    "        A = quickmul(A,k)\n",
    "        # print(A)\n",
    "        return A[1][flag]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:\n",
    "        c = [[0, 0], [0, 0]]\n",
    "        for i in range(2):\n",
    "            for j in range(2):\n",
    "                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (10 ** 9 + 7)\n",
    "        return c\n",
    "\n",
    "    def pow(self, a: List[List[int]], n: int) -> List[List[int]]:\n",
    "        res = [[1, 0], [0, 1]]\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                res = self.multiply(res, a)\n",
    "            a = self.multiply(a, a)\n",
    "            n //= 2\n",
    "        return res\n",
    "\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "\n",
    "        def rabin_krap(text: str, pattern: str, strict: bool=True) -> List[int]:\n",
    "            \"\"\"Rabin-Krap字符串匹配算法\n",
    "            利用Rabin-Krap算法(Rolling hash)实现字符串匹配，时间复杂度O(n+m)，空间复杂度O(1)。\n",
    "            实现时通过多次hash来减少hash碰撞的概率，可以调整mul和mod来切换碰撞。\n",
    "\n",
    "            Args:\n",
    "                text: 文本串\n",
    "                pattern: 模式串\n",
    "                strict: 是否严格匹配，如果为True则会在hash值相同时检查字符串是否匹配，否则只判hash值是否相同\n",
    "            Returns:\n",
    "                模式串在文本串中出现的位置列表\n",
    "            \"\"\"\n",
    "            m, n = len(text), len(pattern)\n",
    "            text_val = [ord(c) - ord('a') for c in text]\n",
    "            pat_val = [ord(c) - ord('a') for c in pattern]\n",
    "            if m < n:\n",
    "                return list()\n",
    "            mul = [133331, 1331]\n",
    "            mod = [int(1e9 + 7), 998244353]\n",
    "            rep = len(mul)  # 重复hash次数\n",
    "            max_mul = [pow(p, n - 1, q) for p, q in zip(mul, mod)]\n",
    "            pat_hash = [0] * rep    # pattern的hash值\n",
    "            for i in range(n):\n",
    "                for j in range(rep):\n",
    "                    pat_hash[j] = (pat_hash[j] * mul[j] + pat_val[i]) % mod[j]\n",
    "            src_hash = [0] * rep\n",
    "            for i in range(n):\n",
    "                for j in range(rep):\n",
    "                    src_hash[j] = (src_hash[j] * mul[j] + text_val[i]) % mod[j]\n",
    "            ans = 0\n",
    "            for i in range(n, m):\n",
    "                if all([p == s for p, s in zip(pat_hash, src_hash)]):\n",
    "                    if not strict or text[i - n:i] == pattern:\n",
    "                        ans += 1\n",
    "                for j in range(rep):\n",
    "                    src_hash[j] = ((src_hash[j] - text_val[i - n] * max_mul[j]) % mod[j] + mod[j]) % mod[j]\n",
    "                    src_hash[j] = (src_hash[j] * mul[j] + text_val[i]) % mod[j]\n",
    "            return ans\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        c = rabin_krap(s + s, t, strict=False)\n",
    "        m = [\n",
    "            [c - 1, c],\n",
    "            [n - c, n - 1 - c]\n",
    "        ]\n",
    "        m = self.pow(m, k)\n",
    "        return m[0][s != t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "def kmp(s, p):\n",
    "    m = len(s)\n",
    "    n = len(p)\n",
    "    s = [''] + list(s)\n",
    "    p = [''] + list(p)\n",
    "    \n",
    "    ne = [0] * (n+1)\n",
    "    i = 2\n",
    "    j = 0\n",
    "    \n",
    "    while i <= n:\n",
    "        while j and p[i] != p[j+1]: j = ne[j]\n",
    "        if p[i] == p[j+1]: j += 1\n",
    "        ne[i] = j\n",
    "        i += 1\n",
    "    \n",
    "    i = 1\n",
    "    j = 0\n",
    "    cnt = 0\n",
    "    while i <= m:\n",
    "        while j and s[i] != p[j+1]: j = ne[j]\n",
    "        if s[i] == p[j+1]: j += 1\n",
    "        \n",
    "        if j == n:\n",
    "            cnt += 1\n",
    "            print(i-n, end=\" \")\n",
    "            j = ne[j]\n",
    "        \n",
    "        i += 1\n",
    "    return cnt\n",
    "\n",
    "def mul(a, b):\n",
    "    x = len(a)\n",
    "    y = len(b)\n",
    "    z = len(b[0])\n",
    "    \n",
    "    res = [[0] * y for i in range(x)]\n",
    "    \n",
    "    for i in range(x):\n",
    "        for j in range(y):\n",
    "            for k in range(z):\n",
    "                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD\n",
    "    \n",
    "    for i in range(x):\n",
    "        for j in range(y):\n",
    "            a[i][j] = res[i][j]\n",
    "    \n",
    "    return a\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        if Counter(s) != Counter(t): return 0\n",
    "        s1 = s + s[:-1]\n",
    "        n = len(s)\n",
    "        x, y = 0, 0\n",
    "        if s == t: y = 1\n",
    "        else: x = 1\n",
    "        cnt = kmp(s1, t)\n",
    "        # print(cnt)\n",
    "        \n",
    "        a = [[n-cnt-1, n-cnt], [cnt, cnt-1]]\n",
    "        res = [[1, 0], [0, 1]]\n",
    "        # print(cnt, a)\n",
    "        while k:\n",
    "            if k & 1: mul(res, a)\n",
    "            k >>= 1\n",
    "            mul(a, a)\n",
    "        # print(x, y)\n",
    "        x, y = res[0][0] * x + y * res[0][1], res[1][0] * x + y * res[1][1]\n",
    "        # print(res)\n",
    "        return y % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "import re\n",
    "\n",
    "def pow(A, n, m):\n",
    "    ret = np.eye(A.shape[0], dtype=int)\n",
    "\n",
    "    while n:\n",
    "        if n & 1:\n",
    "            ret = ret.dot(A) % m\n",
    "        A = A.dot(A) % m\n",
    "\n",
    "        n = n >> 1\n",
    "\n",
    "    return ret\n",
    "\n",
    "def kmp(s, p):\n",
    "    n = len(s)\n",
    "    m = len(p)\n",
    "\n",
    "    match = [0] * m\n",
    "    c = 0\n",
    "    for i in range(1, m):\n",
    "        v = p[i]\n",
    "        while c and p[c] != v:\n",
    "            c = match[c - 1]\n",
    "        \n",
    "        if p[c] == v:\n",
    "            c += 1\n",
    "\n",
    "        match[i] = c\n",
    "\n",
    "    c = 0\n",
    "    ret = 0\n",
    "    for i, v in enumerate(s):\n",
    "        v = s[i]\n",
    "\n",
    "        while c and p[c] != v:\n",
    "            c = match[c - 1]\n",
    "\n",
    "        if p[c] == v:\n",
    "            c += 1\n",
    "        \n",
    "        if c == len(p):\n",
    "            ret += 1\n",
    "            c = match[c - 1]\n",
    "\n",
    "    return ret    \n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        x = s + s[:-1]\n",
    "        n = len(s)\n",
    "\n",
    "        MOD = int(1e9) + 7\n",
    "\n",
    "        c = kmp(x, t)\n",
    "        print(c)\n",
    "\n",
    "        m = np.asarray([\n",
    "            [c - 1, c],\n",
    "            [n - c, n - c - 1]\n",
    "        ])\n",
    "\n",
    "        a = np.asarray([1 if s == t else 0, 1 if s != t else 0])\n",
    "\n",
    "        return int(pow(m, k, MOD).dot(a)[0]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# n-length string s has n transformations, in one operation\r\n",
    "# any transformation can be transformed into other n - 1 transformations\r\n",
    "# dp[i][0] := number of ways after i operations, to transform s to s\r\n",
    "# dp[i][1] := number of ways after i operations, to transform s to one of other n - 1 transformations\r\n",
    "# dp[0] = [1, 0]\r\n",
    "# dp[i][0] = (n - 1)dp[i - 1][1]\r\n",
    "# dp[i][1] = dp[i - 1][0] + (n - 2)dp[i - 1][1]\r\n",
    "# dp[i] = dp[i - 1] * [[0, 1], [n - 1, n - 2]]\r\n",
    "# let M = [[0, 1], [n - 1, n - 2]]\r\n",
    "# dp[i] = dp[0] * M^i\r\n",
    "# let cnt = number of t in n transformation of s\r\n",
    "# if t != s, result is dp[k][1] * cnt\r\n",
    "# if t == s, result is dp[k][0] + dp[k][1] * (cnt - 1)\r\n",
    "import numpy as np\r\n",
    "mod = 1000000007\r\n",
    "mod_arr = np.array([[mod, mod], [mod, mod]])\r\n",
    "\r\n",
    "# KMP\r\n",
    "def kmp(s: str, p: str) -> int:\r\n",
    "    nxt: list[int] = list()\r\n",
    "    n = len(s)\r\n",
    "    m = len(p)\r\n",
    "    if m > 0:\r\n",
    "        nxt.append(0)\r\n",
    "    x = 1\r\n",
    "    now = 0\r\n",
    "    while x < m:\r\n",
    "        if p[now] == p[x]:\r\n",
    "            x += 1\r\n",
    "            now += 1\r\n",
    "            nxt.append(now)\r\n",
    "        elif now:\r\n",
    "            now = nxt[now - 1]\r\n",
    "        else:\r\n",
    "            nxt.append(0)\r\n",
    "            x += 1\r\n",
    "    tar = 0\r\n",
    "    pos = 0\r\n",
    "    ret = 0\r\n",
    "\r\n",
    "    while tar < n:\r\n",
    "        if s[tar] == p[pos]:\r\n",
    "            tar += 1\r\n",
    "            pos += 1\r\n",
    "        elif pos:\r\n",
    "            pos = nxt[pos - 1]\r\n",
    "        else:\r\n",
    "            tar += 1\r\n",
    "\r\n",
    "        if pos == m:\r\n",
    "            ret += 1\r\n",
    "            pos = nxt[pos - 1]\r\n",
    "\r\n",
    "    return ret\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\r\n",
    "        n = len(s)\r\n",
    "        cnt = kmp(s + s[:-1], t)\r\n",
    "        p = np.eye(2, dtype=np.int64)\r\n",
    "        a = np.array([[0, 1], [n - 1, n - 2]], dtype=np.int64)\r\n",
    "\r\n",
    "        while k:\r\n",
    "            if k & 1:\r\n",
    "                p = np.mod(np.matmul(p, a), mod_arr)\r\n",
    "            a = np.mod(np.matmul(a, a), mod_arr)\r\n",
    "            k >>= 1\r\n",
    "\r\n",
    "        dp = np.matmul(np.matmul(np.array([[1, 0]], dtype=np.int64), p),\r\n",
    "                np.array([[1 if s == t else 0], [cnt - (1 if s == t else 0)]], dtype=np.int64))\r\n",
    "\r\n",
    "        return int(dp[0][0] % mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        next = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = next[i-1]\n",
    "            while j >= 0 and t[j] != t[i-1]:\n",
    "                j = next[j]\n",
    "            next[i] = j + 1\n",
    "\n",
    "        valid = []\n",
    "        j = 0\n",
    "        for i in range(2 * n - 1):\n",
    "            c = s[i % n]\n",
    "            if j == n - 1 and c == t[j]:\n",
    "                valid.append(i - n + 1)\n",
    "                j = next[j]\n",
    "            while j >= 0 and c != t[j]:\n",
    "                j = next[j]\n",
    "            j += 1\n",
    "        cnt = len(valid)\n",
    "        if cnt == 0:\n",
    "            return 0\n",
    "\n",
    "        # f[k][0] = cnt of non tar after k ops  f[k][1] = cnt of tar after k ops\n",
    "        # f[k][0] = f[k-1][0] * (n - 1 - cnt) + f[k-1][1] * (n - cnt)\n",
    "        # f[k][1] = f[k-1][0] * cnt + f[k-1][1] * (cnt - 1)\n",
    "        f = [\n",
    "            [n - 1 - cnt, n - cnt],\n",
    "            [cnt, cnt - 1]\n",
    "        ]\n",
    "        y = self.pow(f, k)\n",
    "        return y[1][valid[0] != 0]\n",
    "\n",
    "    def pow(self, f, k):\n",
    "        ret = [\n",
    "            [0, 1],\n",
    "            [1, 0]\n",
    "        ]\n",
    "        while k > 0:\n",
    "            if k & 1:\n",
    "                ret = self.mut(f, ret)\n",
    "            k >>= 1\n",
    "            f = self.mut(f, f)\n",
    "        return ret\n",
    "\n",
    "    def mut(self, f1, f2):\n",
    "        ret = [[0, 0], [0, 0]]\n",
    "        for i in range(2):\n",
    "            for j in range(2):\n",
    "                ret[i][j] = (f1[i][0] * f2[0][j] + f1[i][1] * f2[1][j]) % (10 ** 9 + 7)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Kmp:\n",
    "    \"\"\"kmp算法，计算前缀函数pi,根据pi转移，复杂度O(m+n)\"\"\"\n",
    "\n",
    "    def __init__(self, t):\n",
    "        \"\"\"传入模式串，计算前缀函数\"\"\"\n",
    "        self.t = t\n",
    "        n = len(t)\n",
    "        self.pi = pi = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j and t[i] != t[j]:\n",
    "                j = pi[j - 1]  # 失配后缩短期望匹配长度\n",
    "            if t[i] == t[j]:\n",
    "                j += 1  # 多配一个\n",
    "            pi[i] = j\n",
    "\n",
    "    def find_all_yield(self, s):\n",
    "        \"\"\"查找t在s中的所有位置，注意可能为空\"\"\"\n",
    "        n, t, pi, j = len(self.t), self.t, self.pi, 0        \n",
    "        for i, v in enumerate(s):\n",
    "            while j and v != t[j]:\n",
    "                j = pi[j - 1]\n",
    "            if v == t[j]:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                yield i - j + 1\n",
    "                j = pi[j - 1]\n",
    "\n",
    "    def find_one(self, s):\n",
    "        \"\"\"查找t在s中的第一个位置，如果不存在就返回-1\"\"\"\n",
    "        for ans in self.find_all_yield(s):\n",
    "            return ans\n",
    "        return -1\n",
    "def matrix_multiply(a, b, MOD=10**9+7):\n",
    "    m, n, p = len(a), len(a[0]), len(b[0])\n",
    "    ans = [[0]*p for _ in range(m)]\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            for k in range(p):\n",
    "                ans[i][k] = (ans[i][k]+a[i][j] * b[j][k]) %MOD\n",
    "    return ans \n",
    "def matrix_pow_mod(a, b, MOD=10**9+7):\n",
    "    n = len(a)\n",
    "    ans = [[0]*n for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        ans[i][i] = 1 \n",
    "    while b:\n",
    "        if b & 1:\n",
    "            ans = matrix_multiply(ans, a, MOD)\n",
    "        a = matrix_multiply(a, a, MOD)\n",
    "        b >>= 1\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        if t not in s+s:\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        c = len(list(Kmp(t).find_all_yield(s+s[:-1])))        \n",
    "        m = [\n",
    "            [c-1, c],\n",
    "            [n-c,n-1-c]\n",
    "        ]\n",
    "        m = matrix_pow_mod(m, k)\n",
    "        return m[0][s != t]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class StringAlgorithm:\n",
    "    def findNext(self, s):\n",
    "        pi = [0 for i in range(len(s))]\n",
    "        for i in range(1, len(s)):\n",
    "            j = pi[i-1]\n",
    "            while j > 0 and s[j] != s[i]: j = pi[j-1]\n",
    "            pi[i] = 0 if j == 0 and s[0] != s[i] else j + 1\n",
    "        return pi\n",
    "    def kmp(self, s, t):\n",
    "        pi = self.findNext(t)\n",
    "        m, n, j = len(s), len(t), 0\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            while j >= n or (j > 0 and s[i] != t[j]): j = pi[j-1]\n",
    "            if s[i] == t[j]: j += 1\n",
    "            if j == n: res.append(i - n + 1)\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        n, M = len(s), 10**9 + 7\n",
    "        pos = StringAlgorithm().kmp((s+s)[:-1], t)\n",
    "        f_k = [0, 0]\n",
    "        f_k[1] = (pow(n-1, k, M) + (k % 2 * 2 - 1) + M) * pow(n, M-2, M) % M\n",
    "        f_k[0] = (f_k[1] - (k % 2 * 2 - 1) + M) % M\n",
    "        return sum(f_k[not not p] for p in pos) % M\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        t2 = t + t[0]\n",
    "        pmt = [0] * (n + 1)\n",
    "        j = 0\n",
    "        for i in range(1, n+1):\n",
    "            while j > 0 and t2[i] != t2[j]:\n",
    "                j = pmt[j - 1]\n",
    "            if t2[i] == t2[j]:\n",
    "                j += 1\n",
    "            pmt[i] = j\n",
    "\n",
    "        j = 0\n",
    "        offset = []\n",
    "        for i in range(n*2-1):\n",
    "            while j > 0 and s[i%n] != t[j]:\n",
    "                j = pmt[j - 1]\n",
    "            if s[i%n] == t[j]:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                offset.append(i - n + 1)\n",
    "                j = pmt[j - 1]\n",
    "                \n",
    "        if not offset:\n",
    "            return 0\n",
    "        \n",
    "        tot = len(offset)\n",
    "        \n",
    "        res = [0] * n\n",
    "        for i in offset:\n",
    "            res[i] = 1\n",
    "            \n",
    "        a = -(pow(1-n, k, MOD) - 1) * pow(n, MOD-2, MOD) * tot % MOD\n",
    "        a -= offset[0] == 0\n",
    "        if k % 2 == 0:\n",
    "            a = -a\n",
    "        return a % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Metric:\n",
    "\n",
    "    def __init__(self, x00, x01, x10, x11):\n",
    "        self.m = [[x00 % M, x01 % M], [x10 % M, x11 % M]]\n",
    "\n",
    "    def __mul__(self, other):\n",
    "        return Metric(self.m[0][0] * other.m[0][0] + self.m[0][1] * other.m[1][0],\n",
    "                      self.m[0][0] * other.m[0][1] + self.m[0][1] * other.m[1][1],\n",
    "                      self.m[1][0] * other.m[0][0] + self.m[1][1] * other.m[1][0],\n",
    "                      self.m[1][0] * other.m[0][1] + self.m[1][1] * other.m[1][1])\n",
    "\n",
    "    def pow(self, k):\n",
    "        res = Metric(1, 0, 0, 1)\n",
    "        base = self\n",
    "        while k:\n",
    "            if k & 1:\n",
    "                res = res * base\n",
    "                k -= 1\n",
    "            else:\n",
    "                base = base * base\n",
    "                k //= 2\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        kk = k\n",
    "        \n",
    "        mod = 10**9+7\n",
    "        \n",
    "        base = 31\n",
    "        \n",
    "        s = [ord(c)-ord('a')+1 for c in s]\n",
    "        t = [ord(c)-ord('a')+1 for c in t]\n",
    "        n = len(s)\n",
    "       \n",
    "        def Map(s):\n",
    "            h = 0\n",
    "            for k in range(len(s)):\n",
    "                h = (h * base + s[k]) % mod\n",
    "            return h\n",
    "        \n",
    "        tm = Map(t)\n",
    "        \n",
    "        sm = Map(s)\n",
    "        \n",
    "        d = set()\n",
    "        if sm==tm:\n",
    "            d.add(0)\n",
    "            \n",
    "        for i in range(1,len(s)):\n",
    "            k = s[i-1]\n",
    "            sm = (sm-k*pow(base,n-1,mod))%mod\n",
    "            sm = (sm*base+k)%mod\n",
    "            if sm==tm:\n",
    "                d.add(i)\n",
    "                \n",
    "        \n",
    "        q = len(d)\n",
    "        p = n-q\n",
    "\n",
    "        m = Metric(q-1,q,p,p-1)\n",
    "\n",
    "        m = m.pow(kk)\n",
    "\n",
    "        f0,g0 = (1,0) if 0 in d else (0,1)\n",
    "\n",
    "        return (m.m[0][0]*f0+m.m[0][1]*g0)%M\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "                \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        \"\"\"\n",
    "        KMP的变种（板子）：\n",
    "        给定字符串s和t，返回一个list：所有s中t开头的位置。\n",
    "        \"\"\"\n",
    "        def kmp_search(s: str, t: str) -> list[int]:\n",
    "            # 构建部分匹配表\n",
    "            def get_partial_match_table(pattern: str) -> list[int]:\n",
    "                table = [0] * len(pattern)\n",
    "                length = 0\n",
    "                i = 1\n",
    "                while i < len(pattern):\n",
    "                    if pattern[i] == pattern[length]:\n",
    "                        length += 1\n",
    "                        table[i] = length\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        if length != 0:\n",
    "                            length = table[length - 1]\n",
    "                        else:\n",
    "                            table[i] = 0\n",
    "                            i += 1\n",
    "                return table\n",
    "\n",
    "            if not t:\n",
    "                return []\n",
    "\n",
    "            partial_match_table = get_partial_match_table(t)\n",
    "            i, j = 0, 0\n",
    "            indices = []\n",
    "\n",
    "            while i < len(s):\n",
    "                if t[j] == s[i]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                if j == len(t):\n",
    "                    indices.append(i - j)\n",
    "                    j = partial_match_table[j - 1]\n",
    "                elif i < len(s) and t[j] != s[i]:\n",
    "                    if j != 0:\n",
    "                        j = partial_match_table[j - 1]\n",
    "                    else:\n",
    "                        i += 1\n",
    "\n",
    "            return indices\n",
    "        \n",
    "        # 多接一段s[:-1]，来做循环匹配\n",
    "        start_ids = kmp_search(s+s[:-1], t)\n",
    "        n = len(s)\n",
    "        m = len(start_ids)\n",
    "        # corner case：如果匹配不上，就返回0\n",
    "        if len(start_ids) == 0 :\n",
    "            return 0\n",
    "        \n",
    "        ttt = 10**9+7\n",
    "        a = 1 if 0 in set(start_ids) else 0\n",
    "        b = 1 - a\n",
    "\n",
    "        to_multi = [[1, 0], [0, 1]]\n",
    "        base_t   = [[m-1, m], [n-m, n-1-m]]\n",
    "        \n",
    "        # 2阶 矩阵乘法\n",
    "        def deal_mul(x, y) :\n",
    "            return [[\n",
    "                      (x[0][0]*y[0][0]  + x[0][1]*y[1][0]) % ttt, \n",
    "                      (x[0][0]*y[0][1]  + x[0][1]*y[1][1]) % ttt, \n",
    "                    ], \n",
    "                    [\n",
    "                      (x[1][0]*y[0][0]  + x[1][1]*y[1][0]) % ttt, \n",
    "                      (x[1][0]*y[0][1]  + x[1][1]*y[1][1]) % ttt, \n",
    "                    ]\n",
    "          ]\n",
    "\n",
    "        # 矩阵快速幂\n",
    "        while k > 0 :\n",
    "            if k % 2 == 1 :\n",
    "                to_multi = deal_mul(to_multi, base_t)\n",
    "            k = k // 2\n",
    "            base_t = deal_mul(base_t, base_t)\n",
    "        \n",
    "        return (a * to_multi[0][0] + b * to_multi[0][1]) % ttt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        def kmp_search(s: str, t: str) -> list[int]:\n",
    "            # 构建部分匹配表\n",
    "            def get_partial_match_table(pattern: str) -> list[int]:\n",
    "                table = [0] * len(pattern)\n",
    "                length = 0\n",
    "                i = 1\n",
    "                while i < len(pattern):\n",
    "                    if pattern[i] == pattern[length]:\n",
    "                        length += 1\n",
    "                        table[i] = length\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        if length != 0:\n",
    "                            length = table[length - 1]\n",
    "                        else:\n",
    "                            table[i] = 0\n",
    "                            i += 1\n",
    "                return table\n",
    "\n",
    "            if not t:\n",
    "                return []\n",
    "\n",
    "            partial_match_table = get_partial_match_table(t)\n",
    "            i, j = 0, 0\n",
    "            indices = []\n",
    "\n",
    "            while i < len(s):\n",
    "                if t[j] == s[i]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                if j == len(t):\n",
    "                    indices.append(i - j)\n",
    "                    j = partial_match_table[j - 1]\n",
    "                elif i < len(s) and t[j] != s[i]:\n",
    "                    if j != 0:\n",
    "                        j = partial_match_table[j - 1]\n",
    "                    else:\n",
    "                        i += 1\n",
    "\n",
    "            return indices\n",
    "        \n",
    "        start_ids = kmp_search(s+s[:-1], t)\n",
    "        start_ids = set(start_ids)\n",
    "        n = len(s)\n",
    "        m = len(start_ids)\n",
    "        # print(start_ids)\n",
    "        if len(start_ids) == 0 :\n",
    "            return 0\n",
    "        \n",
    "        ttt = 10**9+7\n",
    "        a = len(start_ids) if not 0 in start_ids else len(start_ids) - 1\n",
    "        b = n-1-a\n",
    "\n",
    "        k -= 1\n",
    "        value = [a, b]\n",
    "        to_multi = [[1, 0], [0, 1]]\n",
    "        base_t   = [[m-1, m], [n-m, n-1-m]]\n",
    "        # print('!', m, n)\n",
    "        # print(k, to_multi, base_t)\n",
    "        \n",
    "        def deal_mul(x, y) :\n",
    "            return [[\n",
    "                      (x[0][0]*y[0][0]  + x[0][1]*y[1][0]) % ttt, \n",
    "                      (x[0][0]*y[0][1]  + x[0][1]*y[1][1]) % ttt, \n",
    "                    ], \n",
    "                    [\n",
    "                      (x[1][0]*y[0][0]  + x[1][1]*y[1][0]) % ttt, \n",
    "                      (x[1][0]*y[0][1]  + x[1][1]*y[1][1]) % ttt, \n",
    "                    ]\n",
    "          ]\n",
    "        while k > 0 :\n",
    "            if k % 2 == 1 :\n",
    "                to_multi = deal_mul(to_multi, base_t)\n",
    "            k = k // 2\n",
    "            base_t = deal_mul(base_t, base_t)\n",
    "            # print(k, to_multi, base_t)\n",
    "        # print(a, b, to_multi[0])\n",
    "        return (a * to_multi[0][0] + b * to_multi[0][1]) % ttt\n",
    "              \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        P = 13331\n",
    "        M = 2**64\n",
    "        MOD= 10**9 + 7\n",
    "\n",
    "        n = len(s)\n",
    "        t_haxi = 0\n",
    "\n",
    "        P_num = [1]\n",
    "        for i in range(n):\n",
    "            P_num.append(P_num[-1] * P % M)\n",
    "            t_haxi = (t_haxi * P + ord(t[i]) - ord(\"a\") + 1) % M \n",
    "\n",
    "        def pre_work(s, P, M):\n",
    "            # 计算所有前缀字符串的哈希值\n",
    "            L = []\n",
    "            L.append(ord(s[0]) - ord(\"a\") + 1)\n",
    "            for i in range(1, len(s)):\n",
    "                L.append((L[-1] * P + ord(s[i]) - ord(\"a\") + 1) % M)\n",
    "            return L\n",
    "\n",
    "\n",
    "        def get_num(L, left, right, M):\n",
    "            # 将求一个子字符串的哈希值转化为两个前缀哈希值相减\n",
    "            res = L[right]\n",
    "            if left > 0:\n",
    "                res -= (L[left - 1] * P_num[right - left + 1])\n",
    "            return res % M\n",
    "\n",
    "        L = pre_work(s, P, M)\n",
    "        match_count = 0  # 匹配的次数\n",
    "        for i in range(1, n):\n",
    "            # 后面一段的哈希加上前面一段的哈希\n",
    "            res = (get_num(L, i, n - 1, M) * P_num[i] % M + get_num(L, 0, i - 1, M)) % M\n",
    "            if res == t_haxi:\n",
    "                match_count += 1\n",
    "        if s == t:\n",
    "            match_count += 1\n",
    "        \n",
    "        # dp[i][0] 表示恰好操作 i 次之后等于 t 的方案数\n",
    "        # dp[i][1] 表示恰好操作 i 次之后不等于 t 的方案数\n",
    "        # dp[i][0] = (match_count - 1) * dp[i - 1][0] + match_count * dp[i - 1][1]\n",
    "        # dp[i][1] = (n - match_count) * dp[i - 1][0] + (n - match_count - 1) * dp[i - 1][1]\n",
    "\n",
    "        def matrix_mul(A, B, MOD):\n",
    "            # 定义矩阵的乘法\n",
    "            # 矩阵 A 为 m * n, 矩阵 B 为 n * p\n",
    "            # 最终结果为 m * p\n",
    "            m = len(A)\n",
    "            n = len(A[0])\n",
    "            p = len(B[0])\n",
    "            res = [[0] * p for _ in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for k in range(p):\n",
    "                        res[i][k] = (res[i][k] + A[i][j] * B[j][k]) % MOD\n",
    "            return res\n",
    "\n",
    "\n",
    "        def quick_mi(mat, k, MOD):\n",
    "            # 矩阵快速幂的初始值设为单位矩阵\n",
    "            ans = [[1, 0], [0, 1]]\n",
    "            while k > 0:\n",
    "                if k & 1 == 1:\n",
    "                    ans = matrix_mul(ans, mat, MOD)\n",
    "                k = k >> 1\n",
    "                mat = matrix_mul(mat, mat, MOD)\n",
    "            return ans\n",
    "        mat = [[match_count - 1, match_count], [n - match_count, n - match_count - 1]]\n",
    "        mat = quick_mi(mat, k, MOD)\n",
    "        if s == t:\n",
    "            return mat[0][0]\n",
    "        else:\n",
    "            return mat[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Python program for KMP Algorithm\n",
    "def KMPSearch(pat, txt):\n",
    "    M = len(pat)\n",
    "    N = len(txt)\n",
    "    ans = []\n",
    " \n",
    "    # create lps[] that will hold the longest prefix suffix \n",
    "    # values for pattern\n",
    "    lps = [0]*M\n",
    "    j = 0 # index for pat[]\n",
    " \n",
    "    # Preprocess the pattern (calculate lps[] array)\n",
    "    computeLPSArray(pat, M, lps)\n",
    " \n",
    "    i = 0 # index for txt[]\n",
    "    while i < N:\n",
    "        if pat[j] == txt[i]:\n",
    "            i += 1\n",
    "            j += 1\n",
    " \n",
    "        if j == M:\n",
    "            ans.append(i-j)\n",
    "            # print (\"Found pattern at index\", str(i-j))\n",
    "            j = lps[j-1]\n",
    " \n",
    "        # mismatch after j matches\n",
    "        elif i < N and pat[j] != txt[i]:\n",
    "            # Do not match lps[0..lps[j-1]] characters,\n",
    "            # they will match anyway\n",
    "            if j != 0:\n",
    "                j = lps[j-1]\n",
    "            else:\n",
    "                i += 1\n",
    "    return ans\n",
    " \n",
    "def computeLPSArray(pat, M, lps):\n",
    "    len = 0 # length of the previous longest prefix suffix\n",
    " \n",
    "    lps[0] # lps[0] is always 0\n",
    "    i = 1\n",
    " \n",
    "    # the loop calculates lps[i] for i = 1 to M-1\n",
    "    while i < M:\n",
    "        if pat[i]== pat[len]:\n",
    "            len += 1\n",
    "            lps[i] = len\n",
    "            i += 1\n",
    "        else:\n",
    "            # This is tricky. Consider the example.\n",
    "            # AAACAAAA and i = 7. The idea is similar \n",
    "            # to search step.\n",
    "            if len != 0:\n",
    "                len = lps[len-1]\n",
    "                # Also, note that we do not increment i here\n",
    "            else:\n",
    "                lps[i] = 0\n",
    "                i += 1\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        MOD = 10 ** 9 +7\n",
    "        idx = KMPSearch(t, s + s)\n",
    "        st = set(i % len(s) for i in idx)\n",
    "        # print(st)\n",
    "        \n",
    "        def mul(a0, a1, b0, b1, n):\n",
    "            c0 = (a0 * b0 % MOD + (n - 1) * a1 * b1 % MOD) % MOD\n",
    "            c1 = (a0 * b1 % MOD + a1 * b0 % MOD + (n - 2) * a1 * b1 % MOD) % MOD\n",
    "            return c0, c1\n",
    "        \n",
    "        # def add(a0, a1, b0, b1, n):\n",
    "        #     return (a0 + b0) % MOD, (a1 + b1) % MOD \n",
    "        \n",
    "        # ^k\n",
    "        def pow_f(a0, a1, n, k):\n",
    "            res0, res1 = 1, 0\n",
    "            while k > 0:\n",
    "                if k & 1:\n",
    "                    res0, res1 = mul(res0, res1, a0, a1, n)\n",
    "                a0, a1 = mul(a0, a1, a0, a1, n)\n",
    "                k >>= 1\n",
    "            return res0, res1\n",
    "        \n",
    "        c0, c1 = pow_f(0, 1, len(s), k)\n",
    "        if 0 not in st:\n",
    "            return (c1 * len(st)) % MOD\n",
    "        else:\n",
    "            return (c1 * (len(st) - 1) + c0) % MOD\n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1000000007 # 998244353\n",
    "\n",
    "def Z_algorithm(s: str):\n",
    "    n = len(s)\n",
    "    Z_alg = [0] * n\n",
    "    Z_alg[0], i, j = n, 1, 0\n",
    "    while i < n:\n",
    "        while i + j < n and s[j] == s[i + j]: j += 1\n",
    "        Z_alg[i] = j\n",
    "        if j:\n",
    "            k = 1\n",
    "            while i + k < n and k + Z_alg[k] < j: Z_alg[i + k], k = Z_alg[k], k + 1\n",
    "            i, j = i + k, j - k\n",
    "        else: i += 1\n",
    "    return Z_alg\n",
    "\n",
    "\n",
    "from typing import List\n",
    "Matrix = List[List[int]]\n",
    "\n",
    "def MatrixMul(mat1: Matrix, mat2: Matrix, mod: int) -> Matrix:\n",
    "    \"\"\" 矩阵相乘 直接在程序主体里实现，比多次调用这个方法快\"\"\"\n",
    "    i_, j_, k_ = len(mat1), len(mat2[0]), len(mat2)\n",
    "    return [[sum(mat1[i][k] * mat2[k][j]\n",
    "                 for k in range(k_)) % mod\n",
    "             for j in range(j_)]\n",
    "            for i in range(i_)]\n",
    "\n",
    "class MatrixPow:\n",
    "    \"\"\" 矩阵快速幂基础版 \"\"\"\n",
    "    def __init__(self, BASE: List[List[int]], MOD=1000000007, P=55) -> None:\n",
    "        \"\"\"\n",
    "        预处理每个 2^n 幂次的状态转移矩阵\n",
    "        :param BASE: 基础状态转移矩阵\n",
    "        :param MOD: 模数\n",
    "        :param P: 计算到 2^P 幂次\n",
    "        \"\"\"\n",
    "        m, n = len(BASE), len(BASE[0])\n",
    "        # assert m == n\n",
    "        self.n = n\n",
    "        self.MOD = MOD\n",
    "        self.M = [BASE] # [[R.copy() for R in BASE]]\n",
    "\n",
    "        for _ in range(P):\n",
    "            T = self.M[-1]\n",
    "            self.M.append([[sum(T[i][k] * T[k][j] for k in range(n)) % MOD for j in range(n)] for i in range(n)])\n",
    "\n",
    "    def trans(self, cur: List[List[int]], exp: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        :param cur: 初始状态矩阵，cur 内有且只有一个一维向量，cur = [[...]]\n",
    "        :param exp: 状态转移次数\n",
    "        :return: 初始状态，经过 exp 次转移后，变成的状态矩阵，也是一个只有一维向量的矩阵\n",
    "        \"\"\"\n",
    "        # assert len(cur) == 1\n",
    "        for b in range(exp.bit_length()):\n",
    "            if exp & 1 << b:\n",
    "                T = self.M[b]\n",
    "                cur = [[sum(cur[0][k] * T[k][j] for k in range(self.n)) % self.MOD for j in range(self.n)]]\n",
    "        return cur\n",
    "\n",
    "    def __pow__(self, exp):\n",
    "        \"\"\" pow(BASE, n, MOD) \"\"\"\n",
    "        cur = [[0] * self.n for _ in range(self.n)]\n",
    "        for i in range(self.n): cur[i][i] = 1\n",
    "        for b in range(exp.bit_length()):\n",
    "            if exp & 1 << b:\n",
    "                T = self.M[b]\n",
    "                cur = [[sum(cur[i][k] * T[k][j] for k in range(self.n)) % self.MOD for j in range(self.n)] for i in range(self.n)]\n",
    "        return cur\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        m, n = len(t), len(s)\n",
    "        ss = t + '#' + s + s\n",
    "        Z = Z_algorithm(ss)\n",
    "        \n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            if Z[m + 1 + i] == m:\n",
    "                c += 1\n",
    "        \n",
    "        if not c:\n",
    "            return 0\n",
    "        \n",
    "        # mp = MatrixPow([[0, 1], [n - 1, n - 2]])\n",
    "        mp = MatrixPow([[c - 1, c], [n - c, n - c - 1]])\n",
    "        R = mp.trans([[1, 0]], k)\n",
    "        # print(R)\n",
    "        return R[0][s != t]\n",
    "        # res = 0\n",
    "        # for i in A:\n",
    "        #     res += R[i > 0]\n",
    "        \n",
    "        # return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "DP, Z-algorithm, Fast mod.\n",
    "Approach\n",
    "How to represent a string?\n",
    "Each operation is just a rotation. Each result string can be represented by an integer from 0 to n - 1. Namely, it's just the new index of s[0].\n",
    "How to find the integer(s) that can represent string t?\n",
    "Create a new string s + t + t (length = 3 * n).\n",
    "Use Z-algorithm (or KMP), for each n <= index < 2 * n, calculate the maximum prefix length that each substring starts from index can match, if the length >= n, then (index - n) is a valid integer representation.\n",
    "How to get the result?\n",
    "It's a very obvious DP.\n",
    "If we use an integer to represent a string, we only need to consider the transition from zero to non-zero and from non-zero to zero. In other words, all the non-zero strings should have the same result.\n",
    "So let dp[t][i = 0/1] be the number of ways to get the zero/nonzero string\n",
    "after excatly t steps.\n",
    "Then\n",
    "dp[t][0] = dp[t - 1][1] * (n - 1).\n",
    "All the non zero strings can make it.\n",
    "dp[t][1] = dp[t - 1][0] + dp[t - 1] * (n - 2).\n",
    "For a particular non zero string, all the other non zero strings and zero string can make it.\n",
    "We have dp[0][0] = 1 and dp[0][1] = 0\n",
    "Use matrix multiplication.\n",
    "How to calculate dp[k][x = 0, 1] faster?\n",
    "Use matrix multiplication\n",
    "vector (dp[t - 1][0], dp[t - 1][1])\n",
    "multiplies matrix\n",
    "[0 1]\n",
    "[n - 1 n - 2]\n",
    "== vector (dp[t][0], dp[t - 1][1]).\n",
    "So we just need to calculate the kth power of the matrix which can be done by fast power algorith.\n",
    "Complexity\n",
    "Time complexity:\n",
    "O(n + logk)\n",
    "Space complexity:\n",
    "O(n)\n",
    "'''\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    M: int = 1000000007\n",
    "\n",
    "    def add(self, x: int, y: int) -> int:\n",
    "        x += y\n",
    "        if x >= self.M:\n",
    "            x -= self.M\n",
    "        return x\n",
    "\n",
    "    def mul(self, x: int, y: int) -> int:\n",
    "        return int(x * y % self.M)\n",
    "\n",
    "    def getZ(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        z = [0] * n\n",
    "        left = right = 0\n",
    "        for i in range(1, n):\n",
    "            if i <= right and z[i - left] <= right - i:\n",
    "                z[i] = z[i - left]\n",
    "            else:\n",
    "                z_i = max(0, right - i + 1)\n",
    "                while i + z_i < n and s[i + z_i] == s[z_i]:\n",
    "                    z_i += 1\n",
    "                z[i] = z_i\n",
    "            if i + z[i] - 1 > right:\n",
    "                left = i\n",
    "                right = i + z[i] - 1\n",
    "        return z\n",
    "\n",
    "    def matrixMultiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(a)\n",
    "        n = len(a[0])\n",
    "        p = len(b[0])\n",
    "        r = [[0] * p for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(p):\n",
    "                for k in range(n):\n",
    "                    r[i][j] = self.add(r[i][j], self.mul(a[i][k], b[k][j]))\n",
    "        return r\n",
    "\n",
    "    def matrixPower(self, a: List[List[int]], y: int) -> List[List[int]]:\n",
    "        n = len(a)\n",
    "        r = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            r[i][i] = 1\n",
    "        x = [a[i][:] for i in range(n)]\n",
    "        while y > 0:\n",
    "            if y & 1:\n",
    "                r = self.matrixMultiply(r, x)\n",
    "            x = self.matrixMultiply(x, x)\n",
    "            y >>= 1\n",
    "        return r\n",
    "\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = self.matrixPower([[0, 1], [n - 1, n - 2]], k)[0]\n",
    "        s += t + t\n",
    "        z = self.getZ(s)\n",
    "        m = n + n\n",
    "        result = 0\n",
    "        for i in range(n, m):\n",
    "            if z[i] >= n:\n",
    "                result = self.add(result, dp[0] if i - n == 0 else dp[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        MAX = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        cnt = 0\n",
    "        # concat_string = s + t + t\n",
    "        def prefix(p):\n",
    "            m = len(p)\n",
    "            pi = [0] * m\n",
    "            j = 0\n",
    "            for i in range(1, m):\n",
    "                while j >= 0 and p[j] != p[i]:\n",
    "                    if j - 1 >= 0:\n",
    "                        j = pi[j-1]\n",
    "                    else:\n",
    "                        j -= 1\n",
    "                j += 1\n",
    "                pi[i] = j\n",
    "                # if j == n:\n",
    "                #     j = pi[n-1]\n",
    "            return pi\n",
    "        \n",
    "        pat = prefix(s + '#' + t + t)\n",
    "        cnt = 0\n",
    "        # print(pat)\n",
    "        for i in range(n):\n",
    "            if pat[i + 2 * n] >= n:\n",
    "                cnt += 1\n",
    "        tt = (s == t)\n",
    "        cnt -= tt\n",
    "        # print(cnt)\n",
    "        if cnt + tt == n:\n",
    "            return pow(n-1, k, MAX)\n",
    "        \n",
    "        def mul(a, b):\n",
    "            return (\n",
    "                (a[0] * b[0] + a[1] * b[2]) % MAX,\n",
    "                (a[0] * b[1] + a[1] * b[3]) % MAX,\n",
    "                (a[2] * b[0] + a[3] * b[2]) % MAX,\n",
    "                (a[2] * b[1] + a[3] * b[3]) % MAX,\n",
    "            )\n",
    "        \n",
    "        def po(M, n, MOD):\n",
    "            result = np.eye(len(M), dtype = np.int64)\n",
    "            while n > 0:\n",
    "                if n%2: result = np.dot(M, result) % MOD\n",
    "                M = np.dot(M, M) % MOD\n",
    "                n //= 2\n",
    "            return result % MOD\n",
    "    \n",
    "        \n",
    "        if k == 1:\n",
    "            return cnt \n",
    "        # elif k == 2:\n",
    "        #     if tt == 0:\n",
    "        #         return (k*(k-1) + (n-1-k) * k)% MAX\n",
    "        #     else:\n",
    "        #         return (k * k + (n-1 -k) * (k + 1)) % MAX\n",
    "        # else:\n",
    "        #     k += tt\n",
    "        #     return pow(n-1, k -2, MAX) * ((n-1 -k) * k + k - 1) % MAX\n",
    "        else:\n",
    "            same, notsame = cnt, n - 1 - cnt\n",
    "            cnt += tt\n",
    "            # while k > 1:\n",
    "            #     same, notsame = (same * (cnt - 1) + notsame * cnt) % MAX, (same * (n-cnt) + notsame * (n-1-cnt)) % MAX\n",
    "            # t = po(np.array([[cnt - 1, cnt], [n - cnt, n - 1 - cnt]]), k - 1, MAX).dot([same, notsame])\n",
    "            k -= 1\n",
    "            a, eye = (cnt-1, cnt, n-cnt, n-1-cnt), (1, 0, 0, 1)\n",
    "            while k > 0:\n",
    "                if k % 2:\n",
    "                    eye = mul(a, eye)\n",
    "                a = mul(a, a)\n",
    "                k //= 2\n",
    "            \n",
    "            return (eye[0] * same + eye[1] * notsame) % MAX\n",
    "                # print(same, notsame)\n",
    "                # k -= 1\n",
    "            # print(t[0])\n",
    "            # t = np.linalg.matrix_power()\n",
    "            # return int(t[0]) % MAX\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "MOD = 10**9+7\n",
    "def mul(m1,m2):\n",
    "    a,b,c,d = m1[0,0],m1[0,1],m1[1,0],m1[1,1]\n",
    "    a1,b1,c1,d1 = m2[0,0],m2[0,1],m2[1,0],m2[1,1]\n",
    "    res = np.mat([[(a*a1+b*c1) % MOD,(a*b1+b*d1) % MOD],\n",
    "                    [(c*a1+d*c1) % MOD,(c*b1+d*d1) % MOD]])\n",
    "    return res\n",
    "global D\n",
    "D = {}\n",
    "def P(matrix,k):\n",
    "    if k in D:return D[k]\n",
    "    if k == 1:return matrix\n",
    "    if not k % 2:\n",
    "        res = mul(P(matrix,k//2),P(matrix,k//2))\n",
    "    else:\n",
    "        res = mul(mul(P(matrix,k//2),P(matrix,k//2)),matrix)\n",
    "    D[k] = res\n",
    "    return res\n",
    "\n",
    "def prep(p):\n",
    "    pi = [0] * len(p)\n",
    "    j = 0\n",
    "    for i in range(1, len(p)):\n",
    "        while j != 0 and p[j] != p[i]:\n",
    "            j = pi[j - 1]\n",
    "        if p[j] == p[i]:\n",
    "            j += 1\n",
    "        pi[i] = j\n",
    "    return pi\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        global D\n",
    "        D = {}\n",
    "        # c = int(s == t)\n",
    "        # n = len(s)\n",
    "        # spre = []\n",
    "        # ssuf = []\n",
    "        # tpre = set()\n",
    "        # tsuf = set()\n",
    "        # for i in range(1,n):\n",
    "        #     spre.append(s[:i])\n",
    "        #     ssuf.append(s[i:])\n",
    "        #     tpre.add(t[:i])\n",
    "        #     tsuf.add(t[i:])\n",
    "        # for i in range(1,n):\n",
    "        #     if s[pre] in tsuf and ssuf in tpre:\n",
    "        #         c += 1\n",
    "        tmp = t + '#' + s * 2\n",
    "        n = len(s)\n",
    "        c = 0\n",
    "        kmp = prep(tmp)\n",
    "        for i in range(len(kmp)):\n",
    "            if kmp[i] == n and i - n * 2 < n:\n",
    "                c += 1\n",
    "\n",
    "        if not c:return 0\n",
    "        if s == t:\n",
    "            res = np.mat([[1,0]])\n",
    "        else:\n",
    "            res = np.mat([[0,1]])\n",
    "        \n",
    "        base = np.mat([[c-1,n-c],\n",
    "                     [c,n-1-c]])\n",
    "        x = 1\n",
    "        while k:\n",
    "            if k % 2:\n",
    "                res *= P(base,x)\n",
    "                res %= 10**9 + 7\n",
    "            x <<= 1\n",
    "            k >>= 1\n",
    "        return int(res[0,0]) \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        M = [[0, 1], [n - 1, n - 2]]\n",
    "        M = powMatrix(M, k)\n",
    "        a, b = 1, 0\n",
    "        a, b = M[0][0] * a + M[1][0] * b, M[0][1] * a + M[1][1] * b\n",
    "        z_st = z_function(s + t)\n",
    "        z_ts = z_function(t + s)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if z_st[i + n] == n - i and z_ts[n - i + n] == i:\n",
    "                ans += b\n",
    "        if k > 1 and z_st[n] == n:\n",
    "            ans += a\n",
    "        return ans % int(1e9 + 7)\n",
    "        \n",
    "def z_function(s):\n",
    "    n = len(s)\n",
    "    z = [0] * n\n",
    "    l, r = 0, 0\n",
    "    for i in range(1, n):\n",
    "        if i <= r and z[i - l] < r - i + 1:\n",
    "            z[i] = z[i - l]\n",
    "        else:\n",
    "            z[i] = max(0, r - i + 1)\n",
    "            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n",
    "                z[i] += 1\n",
    "        if i + z[i] - 1 > r:\n",
    "            l = i\n",
    "            r = i + z[i] - 1\n",
    "    return z\n",
    "        \n",
    "def powMatrix(m, p):\n",
    "    res = [[0] * len(m[0]) for _ in range(len(m))]\n",
    "    for i in range(len(m)):\n",
    "        res[i][i] = 1\n",
    "    t = m\n",
    "    while p:\n",
    "        if p & 1:\n",
    "            res = mulMatrix(res, t)\n",
    "        t = mulMatrix(t, t)\n",
    "        p >>= 1\n",
    "    return res\n",
    "\n",
    "def mulMatrix(m1, m2):\n",
    "    res = [[0] * len(m2[0]) for _ in range(len(m1))]\n",
    "    for i in range(len(m1)):\n",
    "        for j in range(len(m2)):\n",
    "            for k in range(len(m2[0])):\n",
    "                res[i][k] += m1[i][j] * m2[j][k]\n",
    "                res[i][k] %= int(1e9 + 7)\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def prefix_function(s):\n",
    "    n = len(s)\n",
    "    pi = [0] * n\n",
    "    for i in range(1, n):\n",
    "        j = pi[i - 1]\n",
    "        while j > 0 and s[i] != s[j]:\n",
    "            j = pi[j - 1]\n",
    "        if s[i] == s[j]:\n",
    "            j += 1\n",
    "        pi[i] = j\n",
    "    return pi\n",
    "\n",
    "def f(t, s):\n",
    "    cur = s + '#' + t\n",
    "    sz1, sz2 = len(t), len(s)\n",
    "    ret = []\n",
    "    lps = prefix_function(cur)\n",
    "    for i in range(sz2 + 1, sz1 + sz2 + 1):\n",
    "        if lps[i] == sz2:\n",
    "            ret.append(i - 2 * sz2)\n",
    "    return ret\n",
    "\n",
    "\n",
    "\n",
    "# 取模\n",
    "mod = 10**9 + 7\n",
    "def fix(a, b):\n",
    "    n = len(a) \n",
    "    m = len(b[0])\n",
    "    p = len(a[0])\n",
    "    c = [[0]*m for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            t = 0\n",
    "            for k in range(p):\n",
    "                t += a[i][k]*b[k][j]\n",
    "            c[i][j] = (t%mod)\n",
    "    return c \n",
    "\n",
    "\n",
    "def qM(a, j):\n",
    "    n = len(a)\n",
    "    ans = [[0]*n for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        ans[i][i] = 1 \n",
    "    if j==0: \n",
    "        return ans \n",
    "    else:\n",
    "        s = bin(j)[2:][::-1]\n",
    "        st = a \n",
    "        for i in s:\n",
    "            if i=='1':\n",
    "                ans = fix(ans, st)\n",
    "            st = fix(st, st) \n",
    "        return ans \n",
    "    \n",
    "class Solution:\n",
    "    def numberOfWays(self, s: str, t: str, k: int) -> int:\n",
    "        ss = s + s \n",
    "        a = f(ss, t)\n",
    "        if not a:\n",
    "            return 0 \n",
    "        n = len(s) \n",
    "        if s==t:\n",
    "            a.pop() \n",
    "            st = [[1, 0]] \n",
    "        else:\n",
    "            st = [[0, 1]]\n",
    "        use = len(a) \n",
    "        b = [[use-1, n-use], [use, n-use-1]]\n",
    "        b = qM(b, k)\n",
    "        ans = fix(st, b)[0]\n",
    "        return ans[0]%mod\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
